

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

class Solution
{
public:
    string convert(string s, int numRows)
    {
        int n = s.size();
        if (n <= numRows || 1 == numRows || n < 2)
            return s;

        string res;
        int cycle = 2 * numRows - 2;

        for (int i = 0; i < numRows; ++i)
        {
            for (int j = 0; j + i < n; j += cycle)
            {
                res += s[j + i];
                if (i > 0 && i < numRows - 1 && j + cycle - i < n)
                    res += s[j + cycle - i];
            }
        }

        return res;
    }

    string countAndSay1(int n)
    {
        if (1 == n)
            return "1";

        string res("1"), tmp;

        for (int i = 1; i < n; ++i)
        {
            string tmp;

            for (int j = 0, k = j, sn = res.size(); k < sn;)
            {
                while (k < sn && res[k] == res[j])
                {
                    ++k;
                }
                tmp += to_string(k - j);
                tmp += res[j];
                j = k;
            }
            res = tmp;
        }

        return res;
    }

    string countAndSay2(int n)
    {
        if (1 == n)
            return "1";

        string s("1");

        for (int i = 1; i < n; ++i)
        {
            string tmp;
            int cnt = 1, sn = s.size();

            for (int j = 0; j < sn - 1; ++j)
            {
                if (s[j] == s[j + 1])
                    ++cnt;
                else
                {
                    tmp += to_string(cnt);
                    tmp += s[j];
                    cnt = 1;
                }
            }
            if (sn < 2 || s[sn - 1] == s[sn - 2])
            {
                tmp += to_string(cnt);
                tmp += s[sn - 1];
            }
            else
            {
                tmp += to_string(1);
                tmp += s[sn - 1];
            }

            s = tmp;
        }

        return s;
    }

    string countAndSay3(int n)
    {
        if (1 == n)
            return "1";

        string s("11");

        for (int i = 2; i < n; ++i)
        {
            string tmp;
            int cnt = 1, sn = s.size();

            for (int j = 0; j < sn - 1; ++j)
            {
                if (s[j] == s[j + 1])
                    ++cnt;
                else
                {
                    tmp += to_string(cnt);
                    tmp += s[j];
                    cnt = 1;
                }
            }
            if (s[sn - 1] == s[sn - 2])
            {
                tmp += to_string(cnt);
                tmp += s[sn - 1];
            }
            else
            {
                tmp += to_string(1);
                tmp += s[sn - 1];
            }

            s = tmp;
        }

        return s;
    }

    int minNumberOfFrogs(string croakOfFrogs)
    {
        unordered_map<char, int> hash{ {'c', 0}, {'r', 0}, {'o', 0}, {'a', 0}, {'k', 0} };
        unordered_map<char, char> prev{ {'c', 'k'}, {'r', 'c'}, {'o', 'r'}, {'a', 'o'}, {'k', 'a'} };

        for (auto e : croakOfFrogs)
        {
            if (e != 'c' && !hash[prev[e]])
                return -1;

            if (hash[prev[e]])
            {
                --hash[prev[e]];
            }
            ++hash[e];
        }

        if (!hash['c'] && !hash['r'] && !hash['o'] && !hash['a'] && hash['k'])
            return hash['k'];
        else
            return -1;
    }
};

void Test1()
{
    cout << Solution().countAndSay2(4) << endl;
}

int main()
{
    Test1();

	return 0;
}